//
// Created by Tan Ke on 2024/2/12.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

/*
 * 假设有一个滑窗, 从字符串起始地址开始,向右侧滑动直到字符串结束
 * 如果:
 * 滑窗当前字符在滑窗内的字符串中没有重复项, 则说明该次滑动有效, 滑窗大小加一后继续滑动;
 * 滑窗当前字符在滑窗内对字符串中有重复项, 则说明本轮滑窗已经结束, 将字符串起始地址更新到第一个重复项之后, 作为新的滑窗开始滑动
 *
 * 当滑动结束后, 计算所有滑窗的大小, 最大的一个就是最长无重复字符串的长度
 */

struct WindowItem {
    int startIndex;
    int endIndex;
    struct WindowItem* next;
};

struct WindowList {
    struct WindowItem* next;
};

int lengthOfLongestSubstring(char* s)
{
    if (strlen(s) == 0) {
        return 0;
    }

    struct WindowList* windowList = (struct WindowList*)malloc(sizeof(struct WindowList));
    windowList->next = NULL;
    int ret = 0;

    struct WindowItem* item = (struct WindowItem*)malloc(sizeof(struct WindowItem));
    item->startIndex = 0;
    item->endIndex = 0;
    item->next = NULL;
    windowList->next = item;

    for (int i = 1; i < strlen(s); i ++) {
        struct WindowItem* curItem = windowList->next;
        bool newWindow = false;

        for (int j = curItem->startIndex; j < i; j ++) {
            if (s[j] == s[i]) { /* 找到重复项, 此时应该新建一个滑窗 */
                struct WindowItem* newItem = (struct WindowItem*)malloc(sizeof(struct WindowItem));
                newItem->startIndex = j + 1;
                newItem->endIndex = i;
                newItem->next = windowList->next;
                windowList->next = newItem;
                newWindow = true;
                break;
            }
        }
        if (newWindow == false) {
            curItem->endIndex = i;
        }
    }

    struct WindowItem* index = windowList->next;
    while (index != NULL) {
        if (index->endIndex - index->startIndex + 1 > ret) {
            ret = index->endIndex - index->startIndex + 1;
        }
        index = index->next;
    }
    return ret;
}

int main(void)
{
    char* s1 = "abcabcbb";
    printf("%d\n", lengthOfLongestSubstring(s1));

    char* s2 = "bbbbb";
    printf("%d\n", lengthOfLongestSubstring(s2));

    char* s3 = "pwwkew";
    printf("%d\n", lengthOfLongestSubstring(s3));

    return 0;
}